package scheduler;



/**
 * A stub for your Greedy Descent With Restarts scheduler
 */
public class GreedyDescentWithRestartsScheduler extends Scheduler {

	/**
	 * @see scheduler.Scheduler#authorsAndStudentIDs()
	 */
	public String authorsAndStudentIDs() {
		return "Brandon Yuh 28402055\r\nShang Ling Wu 65226060";
	}

	/**
	 * @throws Exception 
	 * @see scheduler.Scheduler#schedule(scheduler.SchedulingInstance)
	 */
	public ScheduleChoice[] solve(SchedulingInstance pInstance) throws Exception {
		ScheduleChoice[] bestScheduleFound = null;
		int fewestViolatedConstraints = Integer.MAX_VALUE;
		
		ScheduleChoice[] localBestScheduleFound = null;
		int localFewestViolatedConstraints = Integer.MAX_VALUE;
		
		
		localBestScheduleFound = initAndRandomize(localBestScheduleFound,pInstance);
		bestScheduleFound = initAndRandomize(bestScheduleFound,pInstance);
		localBestScheduleFound = bestScheduleFound.clone();
		fewestViolatedConstraints = evaluator.violatedConstraints(pInstance, bestScheduleFound);
		localFewestViolatedConstraints = fewestViolatedConstraints;

		
		while( !timeIsUp() && evaluator.violatedConstraints(pInstance, bestScheduleFound)>0 ){
			int initialViolatedConstraints = localFewestViolatedConstraints;
			for(int classIndex = 0; classIndex < localBestScheduleFound.length; classIndex++){
				//localBestScheduleFound[classIndex]
				for(int roomIndex=0; roomIndex<pInstance.numRooms;roomIndex++){
					for(int timeIndex=0; timeIndex<pInstance.numTimeslots;timeIndex++){
						int prevRoom = localBestScheduleFound[classIndex].room;
						int prevTime = localBestScheduleFound[classIndex].timeslot;
						
						localBestScheduleFound[classIndex].room = roomIndex;
						localBestScheduleFound[classIndex].timeslot = timeIndex;
						int newViolations = evaluator.violatedConstraints(pInstance, localBestScheduleFound);
						if(newViolations < localFewestViolatedConstraints){
							localFewestViolatedConstraints = newViolations;
							
						}
						else{
							localBestScheduleFound[classIndex].room = prevRoom;
							localBestScheduleFound[classIndex].timeslot = prevTime;
						}
					}
				}
				//Save as best if it is better
				if(fewestViolatedConstraints > localFewestViolatedConstraints){
					bestScheduleFound = localBestScheduleFound.clone();
					fewestViolatedConstraints = localFewestViolatedConstraints;
				}
				//If we're at the local minima, randomize
				if(initialViolatedConstraints == localFewestViolatedConstraints){
					randomize(localBestScheduleFound,pInstance);
					localFewestViolatedConstraints = evaluator.violatedConstraints(pInstance, localBestScheduleFound);
					
				}
			}
		}
		return bestScheduleFound;
	}
	
	private ScheduleChoice[] initAndRandomize(ScheduleChoice[] schedules, SchedulingInstance pInstance){
		schedules = new ScheduleChoice[pInstance.numCourses];
		for(int courseIndex = 0; courseIndex<pInstance.numCourses; courseIndex++ ){
			schedules[courseIndex] = new ScheduleChoice();
			schedules[courseIndex].room = r.nextInt(pInstance.numRooms);
			schedules[courseIndex].timeslot = r.nextInt(pInstance.numTimeslots);
		}
		
		return schedules;
	}
	
	private ScheduleChoice[] randomize(ScheduleChoice[] schedules, SchedulingInstance pInstance){
		for(int courseIndex = 0; courseIndex<pInstance.numCourses; courseIndex++ ){
			schedules[courseIndex].room = r.nextInt(pInstance.numRooms);
			schedules[courseIndex].timeslot = r.nextInt(pInstance.numTimeslots);
		}
		return schedules;
	}
	

}
